﻿/**
 * Copyright (c) 2011-2016, Mobangjack 莫帮杰 (mobangjack@foxmail.com).
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace util
{
    class LinkedList<T> : IList<T>
    {

        private Node<T> first;
        private Node<T> last;
        private int count;

        public LinkedList()
        {
            first = new Node<T>();
            last = first;
            count = 0;
        }

        public void Add(T item)
        {
            last.data = item;

            Node<T> node = new Node<T>();
            last.rear = node;
            node.front = last;
            last = node;
            count++;
        }

        public void Insert(int index, T item)
        {
            if (index >= count)
            {
                throw new ArgumentOutOfRangeException("index out of range");
            }
            Node<T> node = first;
            for (int i = 0; i < count && node != null; i++, node = node.rear)
            {
                if (i == index)
                {
                    Node<T> tmp = new Node<T>();
                    tmp.data = item;
                    tmp.front = node;
                    tmp.rear = node.rear;
                    node.front.rear = tmp;
                    node.rear.front = tmp;
                }
            }
        }

        public T Remove(int index)
        {
            if (index >= count)
            {
                throw new ArgumentOutOfRangeException("index out of range");
            }
            Node<T> node = first;
            for (int i = 0; i < count && node != null; i++, node = node.rear)
            {
                if (i == index)
                {
                    node.front.rear = node.rear;
                    node.rear.front = node.front;
                    return node.data;
                }
            }
            return default(T);
        }

        public int Remove(T item)
        {
            Node<T> node = first;
            for (int i = 0; i < count && node != null; i++, node = node.rear)
            {
                if (EqualityComparer<T>.Default.Equals(node.data, item))
                {
                    node.front.rear = node.rear;
                    node.rear.front = node.front;
                    return i;
                }
            }
            return -1;
        }

        public T Replace(int index, T item)
        {
            if (index >= count)
            {
                throw new ArgumentOutOfRangeException("index out of range");
            }
            Node<T> node = first;
            for (int i = 0; i < count && node != null; i++, node = node.rear)
            {
                if (i == index)
                {
                    T tmp = node.data;
                    node.data = item;
                    return tmp;
                }
            }
            return default(T);
        }

        public int Replace(T oldItem, T newItem)
        {
            Node<T> node = first;
            for (int i = 0; i < count && node != null; i++, node = node.rear)
            {
                if(EqualityComparer<T>.Default.Equals(node.data, oldItem))
                {
                    node.data = oldItem;
                    return i;
                }
            }
            return -1;
        }

        public int Count()
        {
            return count;
        }

        public T[] ToArray()
        {
            T[] array = new T[count];
            Node<T> node = first;
            for (int i = 0; i < count && node != null; i++, node = node.rear)
            {
                array[i] = node.data;
            }
            return array;
        }

        public int IndexOf(T item)
        {
            Node<T> node = first;
            for (int i = 0; i < count && node != null; i++, node = node.rear)
            {
                if (EqualityComparer<T>.Default.Equals(node.data, item))
                {
                    return i;
                }
            }
            return -1;
        }

        public T Get(int index)
        {
            if (index >= count)
            {
                throw new ArgumentOutOfRangeException("index out of range");
            }
            Node<T> node = first;
            for (int i = 0; i < count && node != null; i++, node = node.rear)
            {
                if (i == index)
                {
                    return node.data;
                }
            }
            return default(T);
        }
    }
}
